查看原文
其他

反编译原理控制流分析

wInFoG_2017 看雪学苑 2023-10-30

说明


最近在整理反编译器设计和实现相关的知识,看看能不能有新的灵感。
发现 vasthao 大哥的《[原创]反编译原理(5)-控制流分析》https://bbs.kanxue.com/thread-247201.htm

这篇文章除了写的不太适合人类阅读(自己学习!),别的都很不错
我觉得这个文章值得写一篇"学习笔记",让我把浅层的内容整理并提取一下,通过举例的方法,更好的解读一下这个技术。

这个笔记将尽量通俗的易懂,不带学术公式的讨论下面这几个问题:
1、控制流还原在反编译器中的功能是什么?
2、鲸书《高级编译器的设计与实现》第7章,讲了啥?
3、举例说明,为什么会出现"不可规约"的控制流
4、为什么IDA/Ghidra等反编译器F5后的代码会有goto,没法完全还原控制流
5、其它的补充。

什么是控制流还原


所谓控制流还原,通俗的讲就是将CFG还原成由if、while、for等组成的高级抽象结构。如下图有个控制流图,他的边本身是个jump,反编译器需要理解控制流的结构,把条件分支和循环识别出来。


反编译器中的控制流还原



控制流还原部分处于反编译步骤的最后几步,在反编译器中端IR优化完成之后,再通过算法将CFG还原成由if、while、for等组成的高级抽象。

《高级编译器的设计与实现》第7章的结构分析技术


鲸书的第七章描述了一个叫做"结构分析"的控制流恢复的算法。其原理大致是预置好各种流图模式,然后在CFG中寻找能对应上的模式后,把流图按照规则进行"塌缩",直到塌缩成一个点就完成分析了。

这样说十分的抽象,举例说明。

预置模式



流图塌缩



什么是"不可规约"流图


使用“结构化分析”这种技术,比较麻烦的问题是对“不可规约”流图的处理。
所谓“不可规约流图”,通俗的说,就是一个CFG无法套用上面任何一种规则进行“塌缩”。

比较典型的“不可规约流图”有多入口的循环,多出口的循环等等,我这里从书里找了几个典型的“不可规约流图”的例子:


为什么会产生不可规约流图?


虽然源码中,不可规约的情况很少很少。但是,在编译的大型二进制产物中,不可规约流图十分常见。

其主要原因是,编译器对源码的优化会修改CFG,产生不可规约的情况,我以比较好理解的编译器的尾融合(tail-merging或cross-jumping)优化为例;
在这个优化中,编译器寻找最后几条指令相同的两个基本块,若这两个基本块都转移到同一个位置,就将这两个基本块的代码尾部合并,以此来缩小编译产物的代码规模。

示例源码:

int fun(int a, int b)
{
int ret = 0;
if (getchar() > 0x10) {
ret = a+b;
} else {
ret = a-b;
if (getchar()>0x20) {
printf("hello");
printf("ret=xx");
return ret;
}
}
printf("hi");
printf("ret=xx");
return ret;
}

编译器优化中发现, printf("ret=xx"); return ret; 这两句代码完全一致,为了减少代码量就插入一个goto语句将这两个尾部进行融合。

int fun(int a, int b)
{
int ret = 0;
if (getchar() > 0x10) {
ret = a+b;
} else {
ret = a-b;
if (getchar()>0x20) {
printf("hello");
goto LABEL
}
}
printf("hi");
LABEL:
printf("ret=xx");
return ret;
}

如下图:


很明显,这就是一个典型的"不可规约"流图,《鲸书》中第七章将也有专门提到这种无法规约的场景。


由于这种流图无法正常规约,那么IDA这种反编译器对付的方法就是插入一个GOTO语句进行缓解。

为什么IDA F5后的代码会有GOTO语句?


当前,通用的反编译器,比如IDA/Ghidra等使用的控制流还原技术都是基于“结构化分析”,为了解决不可规约流图的问题,反编译器选用了一种保守的方案:"删除边"后使用goto替代。并重新进行塌缩。这也是为什么F5后的代码会有GOTO语句的原因。

还是之前那个代码,IDA反编译后会插入goto语句解决这个问题。


简单的说就是下面这样处理:


笔记中没有涉及的部分


1、循环定义、强循环识别、支配树相关的内容与算法;
2、对于"不可规约"流图转换相关的知识;
3、较新的学术论文

如果有兴趣可以自己去看一下鲸书的第七章。




看雪ID:wInFoG_2017

https://bbs.kanxue.com/user-home-985676.htm

*本文为看雪论坛优秀文章,由 wInFoG_2017 原创,转载请注明来自看雪社区


# 往期推荐

1、在 Windows下搭建LLVM 使用环境

2、深入学习smali语法

3、安卓加固脱壳分享

4、Flutter 逆向初探

5、一个简单实践理解栈空间转移

6、记一次某盾手游加固的脱壳与修复




球分享

球点赞

球在看

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存